package com.company;


public class Main {

    public static void main(String[] args) {
        int []arr={34,1,23,345,12,546,131,54,78,6000,321,85,1234,7,16,234,9876};
        quickSort(arr,0,arr.length-1);
        for (int i:arr) {
            System.out.println(i);
        }
    }
    /**
     *
     * @param arr   需要排序的数组
     * @param start 数组索引的开始位置
     * @param end   数组索引的结束位置arr.length-1
     */
    public static void quickSort(int [] arr,int start,int end){
        if (start<end) {
//    拆分索引位
            int index=getIndex(arr,start,end);//index表示索引的数
      /*
       * 注意下边这一块用到了递归，及方法自己调自己
       */
            quickSort(arr,0,index-1);//表示从左边比较
            quickSort(arr,index+1,end);//注意index+1表示从索引的后边以为开始(表示从右边比较)
        }
    }
    /**
     * 分区并返回索引值
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public static int  getIndex(int [] arr,int start,int end){
        int i=start;
        int j=end;
        //挖第一个坑，
        int x=arr[i];//x表示基准数
        while(i<j){
            //先从右向左对比，比大于x的
            while(i<j&&arr[j]>=x){
                j--;
            }
            if (i<j) {
                //把找到的元素放到第一个坑位
                arr[i]=arr[j];
                i++;
            }
            //从左向右对比，比小于x的
            while(i>j&&arr[i]<x){
                i++;
            }
            if (i<j) {
                arr[j]=arr[i];
                j--;
            }
        }
        arr[i]=x;
        return i;
    }

}